package DataStructures;

import java.util.Arrays;

/**
 * Created by msingh on 2014-06-29.
 */
public class MergeSortDuplicate {

    public static void main(String[] args) {
        int[] array = new int[]{31, 22, 45, 67};
        System.out.println("Array Before Sort is: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("Array After Sort is: " + Arrays.toString(array));
    }

    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            int[] left = lefthalf(array);
            System.out.println("Left is: " + Arrays.toString(left));

            int[] right = righthalf(array);
            System.out.println("Right is: " + Arrays.toString(right));

            mergeSort(left);
            mergeSort(right);

            merge(array,left,right);
        }
    }

    public static int[] lefthalf(int[] array) {
        int sizeleft = array.length / 2;
        int[] left = new int[sizeleft];
        for (int i = 0; i < sizeleft; i++) {
            left[i] = array[i];
        }
        return left;
    }
    public static int[] righthalf(int[] array) {
        int sizeleft = array.length / 2;
        int sizeright = array.length - sizeleft;
        int[] right = new int[sizeright];
        for (int i = 0; i < sizeright; i++) {
            right[i] = array[i + sizeleft];
        }
        return right;
    }

    public static void merge(int[] result, int[] left,int[] right){
        int i1 = 0;
        int i2 = 0;

        for(int i=0; i<result.length;i++){
            if(i2>=right.length ||(i1< left.length && left[i1]<right[i2])){
                result[i]=left[i1];
                i1++;
            }
            else{
                result[i]=right[i2];
                i2++;
            }
        }

    }
}
